package algorithm.dp;

public class 正则表达式匹配 {
    /*
     * 给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
     * 
     * '.' 匹配任意单个字符。 '*' 匹配零个或多个前面的元素。 匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
     * 
     * 说明:
     * 
     * s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 示例 1:
     * 
     * 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 示例 2:
     * 
     * 输入: s = "aa" p = "a*" 输出: true 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复
     * 'a' 一次, 字符串可变为 "aa"。 示例 3:
     * 
     * 输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。 示例 4:
     * 
     * 输入: s = "aab" p = "c*a*b" 输出: true 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串
     * "aab"。 示例 5:
     * 
     * 输入: s = "mississippi" p = "mis*is*p*." 输出: false
     */
    public boolean isMatch(String s, String p) {
        /*
         * 如果s[0-i-1]与p[0-j-1]匹配，那么就可以判断s[0-i]与p[o-j-1]是否匹配，s[o-i]与p[o-j]是否匹配
         */
        int lens = s.length();
        int lenp = p.length();
        boolean[][] m = new boolean[lens + 5][lenp + 5];
        // 如果有连续存在的**,则一定不匹配
        if (p.indexOf("**") >= 0) {
            return false;
        }
        // 保证了每个*号前面一定有a-z或者.号
        m[0][0] = true;
        for (int i = 1; i <= lens; i++) {
            for (int j = 1; j <= lenp; j++) {
                if (p.charAt(j - 1) == '.') {
                    m[i][j] = m[i - 1][j - 1];
                }
                if (p.charAt(j - 1) == '*') {
                    if (j != 1) {
                        m[i][j] = p.charAt(j - 1) == p.charAt(i) && m[i - 1][j - 1];
                    } else {
                        m[i][j] = false;
                    }
                } else {
                    m[i][j] = m[i - 1][j - 1] && p.charAt(j - 1) == p.charAt(i - 1);
                }

            }
        }
        return m[lens][lenp];
    }

    boolean dp(String s, int i, String p, int j) {
        if (p.length() == j) {
            return s.length() == i;
        }
        if (s.length() == i) {
            return p.length() == j || (p.length() > 0 && p.length() <= j + 3 && p.charAt(p.length() - 1) == '*');
        }
        return true;
    }

    public static void main(String[] args) {
        正则表达式匹配 run = new 正则表达式匹配();
        run.isMatch("abcab", "ab.*.*.*");
    }
}
